package leetcode_800;

/**
 *@author 周杨
 *ChampagneTower_799 香槟塔往下流香槟 问导入k杯酒  哪一行那一列有多少酒
 *describe:用动态规划 不断往下倒酒
 *2018年10月24日 上午9:40:42
 */
public class ChampagneTower_799_ {
	public double champagneTower(int poured, int query_row, int query_glass) {
        double dp[][]=new double[101][101];
        dp[0][0]=poured;
        for(int i=0;i<=query_row;++i) {
        	for(int j=0;j<=i;++j) {
        		if(dp[i][j]>1) {
	        		double rest=(dp[i][j]-1d)/2d;
	        		dp[i+1][j]+=rest;
	        		dp[i+1][j+1]+=rest;
        		}
        	}
        }
        return Math.min(1, dp[query_row][query_glass]);
    }
}
